A typical content addressable memory (CAM) includes CAM storage elements (core cells) which include comparators therein, so as to perform the dual functions of storage of a bit of data and comparison of the stored bit to applied reference data. Recent prior art includes examples of employing RAM core cells and less than one comparator per storage bit.
U.S. Pat. No. 3,648,254 granted to W. F. Beausoleil on Mar. 7, 1972 discloses the implementation of a CAM using shift registers or other rotating media for storage. They are arranged in such a way as to function as a plurality of word-serial searches operating in parallel. It requires that the stored data rotate past the comparator logic, instead of being read from a RAM based on a rotating pointer.
U.S. Pat. No. 4,145,737 granted to S. M. Lamb et al. on Mar. 20, 1979 discloses the implementation of a CAM using RAM for storage. The comparators are a shared resource, but in a search operation, only one RAM location is selected from each block (the same across all blocks).
U.S. Pat. No. 4,622,653 granted to D. J. McElroy on Nov. 11, 1986 discloses a means of integrating comparators together with a DRAM, accessing all cells in a single row of the DRAM simultaneously (a row referred to as a "block"), thereafter comparing them to reference data, with multiple match lines provided for the multiple words in a physical row, and sequential access means for sequencing through all of the blocks that make up the memory.
U.S. Pat. No. 4,958,377 granted to K. Takahashi on Sep. 18, 1990 discloses many possible embodiments of an associative memory, in which data does not need to be explicitly compared, since the value of a bit is encoded in its position.
A paper by M. Motomura et al. entitled "A 1.2-Million Transistor, 33-MHz, 20-b Dictionary Search Processor (DISP) ULSI with a 160-kb CAM", IEEE Journal of Solid-State Circuits, Vol. 25, No. 5, pp. 1158-1165, October 1990, describes a means of sharing a comparator among multiple SRAM cells using categorization, such that a search is completed in a single cycle, but only one of these SRAM cells is actually compared to the reference data (the one belonging to the selected category). The search of stored data is hence only partial. Though SRAM cells and comparators are grouped into blocks, there are no sub-blocks, no parallel searches per block, and only one match line per column. The match line does not perform any access control function.
A paper by G. J. Lipovski entitled "A Four Megabit Dynamic Systolic Associative Memory Chip", Journal of VLSI Signal Processing, Vol. 4, No. 1, pp. 37-51, 1992 (also U.S. Pat. No. 4,989,180 issued on Jan. 29, 1991), describes a means of storing CAM data in DRAM core cells, which share access to a comparator on a TDM (time division multiplex) basis. The entire contents of the CAM is searched in a single search operation, but the embodiment of this operation is most likely serialized by bit, rather than by word. Row access is controlled by a counter and address signals, rather than shift registers. The plurality of bits belonging to each word are all processed (compared) in the same comparator.
A paper by I. N. Robinson entitled "Pattern-Addressable Memory", IEEE Micro, pp. 20-30, June 1992, describes a structure in which CAM data are stored in DRAM cells, which share a comparator. Access is on a word-by-word basis and is normally performed in some pre-determined order. Rows are selected by address lines and decoders, as controlled by an "array controller", rather than deterministically by shift registers. There is a plurality of blocks on the chip, but each block contains a plurality of complete data words, and blocks are not sub-blocked. Match lines are confined to the "match engine" associated with each block, and do not run above DRAM cells.
U.S. Pat. No. 4,747,072 granted to I. N. Robinson et al. on May 24, 1988 discloses searching circuitry composed of a plurality of "retrieval processors", each with an associated bank of RAM. RAM access is controlled by a shift register, thus arbitrating access to the comparator resource in the processor. Although the access pattern, as controlled by the shift register, is sequential, it is not deterministic (fixed TDM). The processor, itself, may contain considerable circuitry in addition to the comparator, for the intended purpose of controlling the search for a sequence of entries, rather than a single isolated entry.
U.S. Pat. No. 4,794,559 granted to A. J. Greenberger on Dec. 27, 1988 discloses a means of achieving content-addressable functionality using standard DRAM storage array(s). Fixed TDM sharing of the comparator may be employed. Though the memory chip may be divided into separate blocks for the purpose of searching multiple words in parallel, these blocks are oriented such that only a single word line is asserted per cycle (said word line spans a plurality of blocks), and the match line is parallel to the word line, rather than parallel to the bit lines.
In a paper by K. J. Schultz et al. entitled "Architectures for Large-Capacity CAMs", INTEGRATION: the VLSI Journal, Vol. 18, pp. 151-171, 1995 describes, in a general tutorial fashion (pp. 158-161), an architecture employing multiple blocks being searched in parallel.